package 算法练习;/**
 * @author： li
 * @date： 2022-01-05 18:29
 * @version 1.0
 */

import java.util.Scanner;
/**
 问题描述
 　　有一个N x N的方格,每一个格子都有一些金币,
 只要站在格子里就能拿到里面的金币。
 你站在最左上角的格子里,
 每次可以从一个格子走到它右边或下边的格子里。
 请问如何走才能拿到最多的金币。
 输入格式
 　　第一行输入一个正整数n。
 　　以下n行描述该方格。金币数保证是不超过1000的正整数。
 输出格式
 　　最多能拿金币数量。
 样例输入
 3
 1 3 3
 2 2 2
 3 1 2
 样例输出
 11
 数据规模和约定
 　　n<=1000
 */
public class 拿金币_DP {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            //in.nextLine(); // 去除回车的影响，如果第一个读入的是数字，接下来读入的是字符，那么注意回车的影响
            int[][] arr = new int[n][n];
            for(int i=0; i<n; i++) {
                //String[] s = in.nextLine().trim().split(" ");
                for(int j=0; j<n; j++) {
                    //arr[i][j] = Integer.parseInt(s[j]);
                    arr[i][j] = in.nextInt();
                    if (j==n-1)in.nextLine();
                }
            }

//		可以设置不从0开始，只需要设置多一行多一列的数组结构就可，就不需要判断条件了
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    int left = j-1<0 ? 0 : arr[i][j-1]; // 判断是否在边缘
                    int up = i-1 < 0 ? 0 : arr[i-1][j]; // 判断是否在边缘
                    arr[i][j] = Math.max(left,up) + arr[i][j];  // 每一个元素的最大值都是通过上方和左方得到的
//                    for(int p=0; p<n; p++) {
//                        for(int m=0; m<n; m++) {
//                            System.out.print(arr[p][m]+" ");
//                            if(m==n-1) System.out.println(" ");
//                        }
//                    }
//                    System.out.println(" ");
                }
            }
            System.out.print(arr[n-1][n-1]);
        }

}
